Forum:Distributed project on BB(5)
Last time I explored remaining 5-state undecided TMs to be halting, using the force of computer program. We can sufficiently accelerate that process if we should do it together (like members of GIMPS in prime number searches). Anyone interested in improving the bound for \(\Sigma(5)\)? I mean just run one of TMs on your computer, so you haven't to do anything constanly (well, it can slow your computer a bit if it's too weak). The list of undecided TMs you can find here and here. Ikosarakt1 (talk ^ ) 16:57, September 7, 2013 (UTC) :This project would have basically zero practical application, so I wouldn't expect very many volunteers. I'd be happy to help, though. FB100Z • talk • 17:21, September 7, 2013 (UTC) ::Okay, but we, being fans of googology probably interested in improving bounds. In addition, we shall make our GWiki pretty glorious if we should discover it (as this bound will be in Wikipedia). Ikosarakt1 (talk ^ ) 21:29, September 7, 2013 (UTC) :Using this simulator I found that TM#827123 doesn't halt after 238,418,940 steps and leaves more than 19,978 1's on the tape. Wythagoras (talk) 17:34, September 7, 2013 (UTC) :What's the most efficient algorithm you know for simulating a TM? FB100Z • talk • 18:01, September 7, 2013 (UTC) ::I don't see how we can simulate TM faster than just step-by-step running unless the function which it computes is known exactly. For HNR typed TMs we must perform step-by-step algorithm on the computer program. Ikosarakt1 (talk ^ ) 21:28, September 7, 2013 (UTC) :::Method used for finding bounds used macro machine, together with subroutines searching for repetitions. I believe 5-state HNR's have some type of regularity to them, so some machine-assisted checking would show this. LittlePeng9 (talk) 21:49, September 7, 2013 (UTC) :::True, but creating such a program would be pretty hard work I believe. Can you verify, for example, TM#827123 using this method? Ikosarakt1 (talk ^ ) 21:54, September 7, 2013 (UTC) :I found that TM#2523420 doesn't halt after 75 billion steps. Wythagoras (talk) 18:51, September 7, 2013 (UTC) ::Thanks, but I don't recommend you to use this simulator if you want to run TM for really large number of steps, since it overflows after 2147483647 steps. The better thing is made up your own program in the background like Lazarus. I done it, and I'm planning to run TM#827123 up to 10 trillionth step (over 2 trillion have been performed already). Ikosarakt1 (talk ^ ) 19:27, September 7, 2013 (UTC) ::I believe HNR#7 doesn't halt. It has a loop: State 5-3-1-3-1-3-4-1-2-5-3-1-3-1-3-4-1-2 Wythagoras (talk) 06:48, September 8, 2013 (UTC) ::Are "state-loop" enough to prove TM to be non-halting? There must be also repeating condition for tape. Ikosarakt1 (talk ^ ) 11:54, September 8, 2013 (UTC) :::No, but there is also a repeating string on the tape, for more information you can look here. :::Wythagoras (talk) 13:08, September 8, 2013 (UTC) TM#34605254 (HNR#35) I ran TM#34605254 (HNR#35) and it doesn't halt after 2.75e12 steps. (rate: 5e9 steps/second) -- ☁ I want more ⛅ 08:59, September 9, 2013 (UTC) :Thanks! I've calculated that it has been done with 9 minutes 10 seconds. Ikosarakt1 (talk ^ ) 10:14, September 9, 2013 (UTC) HNR#35 exhibits 4-ary counting behavior, and currently (around after 10,000 steps) it is counting with 33 "digit-holders", each consisting of 2 digits between 11's. For example, in step 13419, the tape's content is: 0(68 0's)11'00'11'00'11'01'11'00'11'00'11'00'11'00'11'00'(25 1100's)11111001100110011010111011 Where the head is on the leftmost 0 and in state 2 (starting from 0). You can see that the third from the left digit is 2, and all other digits are 0. Based on this observation, I guess that if this TM ever halts, it will not happen in the next 1040 steps. -- ☁ I want more ⛅ 14:11, September 9, 2013 (UTC) :By the way, this TM reminds me of Forever Endeavor... -- ☁ I want more ⛅ 14:16, September 9, 2013 (UTC) :I expect that exact value of S(5) will lie somewhere in the exponential range, so I doubt that it halts. We can't be sure, however. Ikosarakt1 (talk ^ ) 17:02, September 9, 2013 (UTC) HNR#16 & HNR#19 These TMs actually have similar behavior. I noted that they halt when head finds two 1's (or rows of 1's) separated by only one space and TM has the state either 3 or 4, head placed on the first 1. Can anyone prove that this situation won't ever happen? Ikosarakt1 (talk ^ ) 17:02, September 9, 2013 (UTC) I think I can prove it for HNR#19, but I can't for HNR#16. The only way to come in state 3 is via state 2. There must be a 1 under the head, so the one to the right must also be a one. However, that's impossible, since you had to enter state 2 using state 1, which would have left a blank on the tape. Wythagoras (talk) 17:40, September 9, 2013 (UTC) Noob question What's the standard way of enumerating TMs? When we say TM#x, what's the ruleset given x? FB100Z • talk • 18:38, September 10, 2013 (UTC) There is no "standard" way. One of ways is Wolfram's numbering, but we can do it in many different ways. LittlePeng9 (talk) 19:01, September 10, 2013 (UTC) :What's the rule for Wolfram's numbering? FB100Z • talk • 19:58, September 10, 2013 (UTC) HNR#42 How about this counter? For me, it seems that it just a binary counter where "11111"'s works like "1"'s, representing a single bit. "11 11"'s and spaces works like digit-separators. I don't expect that it halts, but a strict proof would be pleased. Ikosarakt1 (talk ^ ) 17:59, September 12, 2013 (UTC) I ran the machine for 100,000 steps and I saw a pattern: 111 11 111 11 111 11 111 11 ... Wythagoras (talk) 18:09, September 12, 2013 (UTC)